import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=93 lang=java
 *
 * [93] 复原IP地址
 *
 * https://leetcode-cn.com/problems/restore-ip-addresses/description/
 *
 * algorithms
 * Medium (46.20%)
 * Likes:    217
 * Dislikes: 0
 * Total Accepted:    32.6K
 * Total Submissions: 70.5K
 * Testcase Example:  '"25525511135"'
 *
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * 
 * 示例:
 * 
 * 输入: "25525511135"
 * 输出: ["255.255.11.135", "255.255.111.35"]
 * 
 */

// @lc code=start
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        if(s == "" || s.length()>12) {
            return res;
        }
        dfs(s, new ArrayList<String>(), res);
        return res;
    }

    void dfs(String s, List<String> temp, List<String> res) {
        //截至条件
        if (temp.size() == 4 && s.length()==0) {
            String ip = String.join(".", temp);
            res.add(ip);
            return;
        }

        //遍历候选人
        for (int i=1 ; i<4 ; i++) {
            if (i <= s.length()) {
                String e = s.substring(0, i);
                //筛选条件
                if(Integer.parseInt(e) <=255 && (e.equals("0") || !e.startsWith("0"))) {
                    temp.add(e);
                    //把已经用过的字符去掉，将剩余字符传入下一次过程
                    dfs(s.substring(i), temp, res);
                    temp.remove(temp.size() - 1);
                }
            }

        }

    }
}
// @lc code=end

